A number of methods have been used to model the reliability of a complex system. Some of the more relevant methods can be divided into four categories: Boolean logic methods, a problem-specific model written with a general purpose package (e.g. MATLAB), a hybrid of a Boolean logic methods and a problem specific model, and Petri nets.
Boolean Logic Methods
There are two main frameworks that are based on Boolean logic: Reliability Block Diagrams (RBDs) and Fault Tree Analysis (FTA). Together they dominate safety and reliability modeling with the former being more often applied to system reliability, while the latter are more prevalent in the context of safety and Probabilistic Risk Assessment (PRA). RBDs comprise connected-together blocks representing components of a system. The source (input) is usually located at the left of the diagram, and the sink (output) at the right. When a part fails in accordance with a given distribution, the “flow” through the corresponding block stops. If there is an uninterrupted path from the source to the sink, the system is up. Otherwise, the system is down. This representation naturally allows for modeling redundancy. In its standard form, FTA relies on two logical “gates” (“AND” and “OR”) to combine “basic events” (i.e., leaves of the tree) into the “top-level event” (root of the tree). This allows evaluating the probability of a top-level event based on given probabilities for basic events.
There are several commercially available tools that are easy to use which provide an intuitive way to build an RBD or conduct FTA such as the “Relex Reliability Block Diagram” and “Relex Fault Tree/Event Tree” software packages produced by Relex Software, Inc. of Greensburg, Pa., and “AvSim+” software produced by Isograph, Inc. of Newport Beach, Calif. However, none of these tools provide the flexibility to model all the important features of systems (e.g. cascading failure effects and the use of new parts) since the modeling of these features is intimately related to the dynamic interactions between the components.
Problem Specific Models
A problem-specific model may be written in a general purpose package such as MATLAB. Such models are very flexible but are expensive to develop, and the complexity becomes prohibitive for large-scale applications since the transparency and simplicity of RBD modeling is lost. Additionally, the reusability of such models is very limited.
Hybrid Boolean Logic and Problem Specific Models
One potential solution to modeling complex reliability systems is using a hybrid of the first two methods. For example, one hybrid solution is implemented in the “Spar” software produced by Clockwork Solutions, Inc. of Austin, Tex. The Clockwork Solutions approach uses RBD modeling supplemented with a proprietary macro language that can be difficult to understand and use. Because the macro language tends to have a steep learning curve, many clients request Clockwork Solutions create customized models rather than customizing the models themselves. This can result in labor intensive models that may be high in direct and indirect costs. Furthermore, the extensive reliance on non-graphical modeling means results in hiding important model features from the user (such as dependencies among components' failures), which may adversely affect verification procedures and the compatibility with other reliability analyses. Despite all these drawbacks, the software is widely used because of the lack of viable alternatives for modeling the reliability of a large complex system.
Petri Net Extension Formalism
One other potential solution for modeling system reliability is the use of a Petri net extension. However, most of the available tools for Petri nets are limited to modeling stochastic processes governed by firing policies with an exponential distribution where memory issues are not addressed. The research related to handling aging systems is much more recent and limited in scope.
Petri nets have been used for over forty years to model processes. Although extensions to the basic Petri net have been developed, and are briefly described below, the essential components and behavior are essentially the same. A Petri net is a directed graph with two disjoint types of nodes: places (denoted as circles) and transitions (denoted as rectangles). A directed arc (an arc denoted as a line with an arrow), can connect a place to a transition or a transition to a place. A directed arc that connects a place to a transition is called an input arc, and a directed arc that connects a transition to a place is called an output arc. The places connected to a given transition by input or output arcs are called the input or output places, respectively, for this transition.
An arc from a place to a transition indicates that the transition requires one token in that place as one of the conditions for it to be enabled. However, in some extensions of the Petri net, arc multiplicities (integer numbers) can be specified as well. That is, the multiplicity of the arc denotes the number of tokens from that place that the transition requires to be enabled. These arcs are denoted with a “/” and an integer number representing the respective multiplicity.
Each place may be assigned a non-negative number of tokens (denoted as small, solid circles within a place). Thus, each place is capable of hosting zero or more assigned tokens. A combined assignment for all the places in the model is referred to as a marking of the system that fully characterizes the system. Changes in the system state are modeled by the tokens' movements that are realized from the transitions' “firing.” The firing of a transition simultaneously accomplishes two actions: (1) it removes at least one token from its input places and (2) deposits at least one token to its output places. The quantities of removed and deposited tokens are equal to the multiplicities of the corresponding input and output arcs, respectively.
Generally speaking, the number of removed and deposited tokens does not have to coincide, and these two parts of firing can be considered as independent events corresponding to the “death” and “birth” of the tokens, respectively. However, a combination of a token's removal from an input place and a token's deposit into an output place for the same transition may also considered as a single action of moving the token from the input place to the output place. If all the tokens are indistinguishable, then both interpretations are equivalent. For labeled tokens, the difference may be significant, since it allows the preservation of information stored in the label as the token moves from one place to another.
The firing of a transition can only occur when the transition is enabled. The first condition for a transition to be enabled is the requirement that each of the transition's input places have at least as many tokens as the multiplicity of the corresponding input arcs. However, some additional conditions on the system marking can be imposed as well (e.g., so-called “guards”), and the flexibility of these conditions depends on the Petri net extension. For example, one type of guard is an inhibitor arc (denoted as an arc terminated with a small hollow circle). Although an inhibitor arc does not increase the Petri net's representation power, inhibitor arcs can make the model more compact and understandable.
Thus, in the presence of inhibitor arcs, there is an additional condition for a transition to become enabled. Specifically, a transition having an inhibitor may be enabled only when all of the inhibitor input places for that transition have fewer numbers of tokens than the multiplicities of the corresponding inhibitor arc(s).
Original Petri nets did not maintain a concept of time. Rather, an enabled transition would fire instantaneously. However, Petri net extensions introduced deterministic time delays in which the firing of a transition occurs when a transition is enabled for a specified amount of time. These extensions led to timed Petri nets, and then were later extended to stochastic Petri nets in which the delays may be random variables based on given distributions.
In a standard stochastic Petri nets, when a transition is disabled, it “forgets” its previous enabled time. The time is reset when the transition is enabled again and the corresponding firing time is resampled. This memory policy is referred to as an “enabling memory” or a “preemptive repeat different” (prd) policy. In a second type of memory policy, a transition can “remember” the time that it was enabled. In effect, the transition's timer is stopped but not reset. This is called an “age memory” or a “preemptive resume” (prs) policy. Finally, using a third type of memory policy, a transition is configured such that the timer is reset, but no resampling is done and the same sampled time is used. This third memory policy is called a “preemptive repeat identical” (pri) policy.
Another extension, referred to as a “colored” Petri net extension, uses colored tokens to identify the token. The firing policy of the transition can be affected by the color of the token. This concept is quite different from standard Petri nets which treat the tokens as fungible objects which are not identified. The tokens in a colored Petri net may change with a change in marking, such as, upon firing of a transition. Thus, a token in a colored Petri net does not carry any information about the duration the token stays at a particular place. Additionally, since the labels (colors) that can affect firing policies can only change in a discrete fashion when a token is moved from one location to another, the properties of the token stay the same so long as the token remains in the same place.
Accordingly, prior art Petri net modeling systems use memory-enabled transitions, which can be an efficient way to model certain types of systems. However, because prior art standard Petri nets (including any extensions thereof), do not have a simple way to track the age, or other relevant property, of a part (which degrades) in a complex system, prior art Petri nets are not efficient for modeling the reliability and performability of a system.
U.S. patent application Ser. No. 10/043,712 (now U.S. Pat. No. 7,006,947) entitled “Method and Apparatus for Predicting Failure in a System,” and U.S. Pat. No. 6,321,187 entitled “System Reliability Assessment Tool” cover various aspects of system reliability, but do not mention the use of Petri nets. At the same time, several patents are apparently devoted to various applications of Petri nets, but are not related specifically to systems reliability. For example, U.S. Pat. No. 6,185,469 entitled “Method and Apparatus for Testing and Controlling a Flexible Manufacturing System,” U.S. Pat. No. 6,363,494 entitled “System and Method for Characterizing and Repairing Intelligent Systems,” and U.S. Pat. No. 6,067,357 entitled “Telephony Call-Center Scripting by Petri Net Principles and Techniques.” Furthermore, an application of colored Petri nets is described in U.S. Pat. No. 5,257,363 entitled “Computer Aided Generation of Programs Modeling Complex Systems Using Colored Petri Nets,” which describes an implementation of a colored Petri nets as applied to solving a specific problem. However, each of these works rely on existing Petri nets, and extensions of Petri nets, to apply their respective solutions.
Thus, what is needed is a Petri net extension which can more efficiently apply the Petri net formalism to applications in which time accumulation affects a system's behavior, such as, but not limited to: probabilistic risk assessment and modeling system reliability, safety, and security, modeling the spread of viruses and infectious diseases. For example, in the context of epidemiological modeling, a token can represent an individual, with different places corresponding to various states of his or her health as well as any contacts with other individuals and/or medication effects. Then aging tokens can represent the individual's life expectancy or the time since the decease has been contracted. Without the use of aging tokens such information would be lost as soon as the token moves to a new place, which would severely limit the use of token's movements.